use std::collections::HashSet;
use rand::Rng;
// 使用一个静态的可变变量来缓存已知的素数
static mut KNOWN_PRIMES: Option<HashSet<u128>> = None;

/// 快速幂计算 a^b % m
pub fn quick_pow(mut a: u128, mut b: u128, m: u128) -> u128 {
    let mut result = 1;
    a %= m;
    while b > 0 {
        if b & 1 == 1 {
            result = result * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    result
}

/// 米勒-拉宾素性测试
fn miller_rabin(n: u128, test_times: usize) -> bool {
    if n < 2 { return false; }
    if n == 2 || n == 3 { return true; }
    if n % 2 == 0 || n % 3 == 0 { return false; }

    let mut u = n - 1;
    let mut t = 0;
    while u % 2 == 0 {
        u >>= 1;
        t += 1;
    }

    let mut rng = rand::thread_rng();
    for _ in 0..test_times {
        let a = rng.gen_range(2..=n-2);
        let mut v = quick_pow(a, u, n);
        if v == 1 || v == n - 1 { continue; }

        let mut s = 0;
        while s < t - 1 {
            v = quick_pow(v, 2, n);
            if v == n - 1 { break; }
            s += 1;
        }
        if v != n - 1 { return false; }
    }
    true
}

/// 综合素性测试函数
pub fn is_prime(n: u128) -> bool {
    if n <= 1 {
        return false;
    }
    if n <= 3 {
        return true;
    }
    if n % 2 == 0 || n % 3 == 0 {
        return false;
    }
    if n < 1000000 {
        // 对于较小的数，使用试除法
        let mut i: u128 = 5;
        while i * i <= n {
            if n % i == 0 || n % (i + 2) == 0 {
                return false;
            }
            i += 6;
        }
        return true;
    } else {
        // 对于较大的数，使用米勒-拉宾素性测试
        return miller_rabin(n, 8); // 测试次数可以根据需要调整
    }
}
pub fn min_edge_prime_num(number: u32) -> String {
    // 初始化静态变量
    unsafe {
        if KNOWN_PRIMES.is_none() {
            KNOWN_PRIMES = Some(HashSet::new());
        }
    }

    let mut edge_length: u128 = 3;
    let mut num_primes: u128 = 0;
    let mut total_diagonals: u128 = 1;
    let mut last_number: u128 = 1;

    loop {
        for _ in 0..4 {
            last_number += edge_length - 1;
            let primes = unsafe { KNOWN_PRIMES.as_mut().unwrap() };
            if primes.contains(&last_number) || is_prime(last_number) {
                num_primes += 1;
                primes.insert(last_number);
            }
            total_diagonals += 1;
        }

        let prime_ratio: f64 = (num_primes as f64) / (total_diagonals as f64);
        if prime_ratio < (number as f64) / 100.0 {
            break;
        }

        edge_length += 2;
    }

    format!("{},{}", edge_length, num_primes)
}